package com.zhugang.week09;

import java.util.*;

/**
 * @program algorithms
 * @description: canFinish
 * @author: chanzhugang
 * @create: 2022/08/23 16:08
 */
public class CanFinish {

    /**
     * 207 课程表： 拓扑排序，看是否存在环
     * 拓扑排序算法：Kahn算法
     *
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 拓扑排序， 没看明白
        // 构建邻接表
        List<Integer> adjs[] = new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            adjs[i] = new ArrayList<>();
        }

        // 入度
        int[] indegress = new int[numCourses];
        for (int i = 0; i < prerequisites.length; i++) {
            adjs[prerequisites[i][1]].add(prerequisites[i][0]);
            indegress[prerequisites[i][0]]++;
        }
        List<Integer> zeroInDegress = new LinkedList<>();
        for (int i = 0; i < indegress.length; i++) {
            if (indegress[i] == 0) {
                zeroInDegress.add(i);
            }
        }

        // kahn算法
        int zeroInDegressCount = 0;
        while (!zeroInDegress.isEmpty()) {
            // 此处代码有问题

            int coursei = zeroInDegress.remove(0);
            zeroInDegressCount++;
            for (Integer coursej : adjs[coursei]) {
                // 入度-1
                indegress[coursej]--;
                if (indegress[coursej] == 0) {
                    zeroInDegress.add(coursej);
                }
            }
        }
        return zeroInDegressCount == numCourses;
    }

}